//
//  Problem229.swift
//  LeetCode
//
//  Created by 武侠 on 2023/6/27.
//  Copyright © 2023 zhulongiMac02. All rights reserved.
//

import UIKit

/*
 229. 多数元素 II 中等
 给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
 示例 1：
     输入：nums = [3,2,3]
     输出：[3]
 示例 2：
     输入：nums = [1]
     输出：[1]
 示例 3：
     输入：nums = [1,2]
     输出：[1,2]
 提示：
 1 <= nums.length <= 5 * 10^4
 -10^9 <= nums[i] <= 10^9

 进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
 */
class Problem229: NSObject {
    /*
     摩尔投票法
     */
    func majorityElement(_ nums: [Int]) -> [Int] {
        var firstValue = 0, firstNumber = 0
        var secondValue = 0, secondNumber = 0
        for n in nums {
            if firstNumber > 0, n == firstValue {
                firstNumber += 1
            } else if secondNumber > 0, n == secondValue {
                secondNumber += 1
            } else if firstNumber == 0 {
                firstValue = n
                firstNumber += 1
            } else if secondNumber == 0 {
                secondValue = n
                secondNumber += 1
            } else {
                firstNumber -= 1
                secondNumber -= 1
            }
        }
        
        var firstCnt = 0
        var secondCnt = 0
        for n in nums {
            if n == firstValue {
                firstCnt += 1
            } else if n == secondValue {
                secondCnt += 1
            }
        }
        
        var result:[Int] = []
        if firstNumber > 0, firstCnt > nums.count / 3 {
            result.append(firstValue)
        }
        if secondNumber > 0, secondCnt > nums.count / 3 {
            result.append(secondValue)
        }
        
        return result
    }
}
